package LearnDataStructure.d_图结构.f_最短路径by单元;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-15 20:07
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.f_最短路径by单元
 */
/*
bellman-ford算法
遍历所有的边，边有起点i和终点j，
如果源点到顶点的最短距离d[i]已经算出来，就比较d[j]和d[i]+cost，
如果前者比后者大，就可以更新d[j]

如此往复，直到没有数据可更新，这样源点到所有顶点的最短距离就算出来了
 */

/**
 * 适用于有向单边图
 * 有起点的说法，算法要的结果，只是start到end的最短的权值的边的集合！！！将来的我听着：这就是Kruskal与最短路径算法的区别
 */
public class g_BellmanFord {
    public static void main(String[] args) {
        int[][] graph = {
               //a  b  c  d  e  f  g
                {0, 2, 5, 0, 0, 0, 0},  //0a
                {2, 0, 4, 6, 10, 0, 0}, //1b
                {5, 4, 0, 2, 0, 0, 0},  //2c
                {0, 6, 2, 0, 0, 1, 0},  //3d
                {0, 10, 0, 0, 0, 3, 5}, //4e
                {0, 0, 0, 1, 3, 0, 9},  //5f
                {0, 0, 0, 0, 5, 9, 0}   //6g
        };

        g_BellmanFord test = new g_BellmanFord();
        int[] distance = test.bellmanFord(0, graph);//从a节点开始
        for (int i = 0; i < distance.length; i++) {
            System.out.println("a -> " + (char)('a' + i) + " 最短距离: " + distance[i]);
        }
    }


    public int[] bellmanFord(int start, int[][] graph) {
        int N = graph.length;
        //start到各顶点的最短距离；下标代表节点的抽象表示，例如下标0代表节点a
        int[] result = new int[N];//
        //初始化result[]
        for (int i = 0; i < N; i++) {
            result[i] = Integer.MAX_VALUE;//全设置成正无穷
        }
        //start距离start的距离是0
        result[start] = 0;
        //死循环离开标志
        boolean update = false;
        while (true) {
            update = false;
            for (int i = 0; i < N; i++) {
                //如果start节点到i节点的最短距离还没算出来
                if (result[i] == Integer.MAX_VALUE) {
                    continue;
                }
                /*
                开始判断从i节点到j节点的所有可能距离
                因为不知道i节点与哪个其他的节点有边
                所以采用for循环穷举
                 */
                for (int j = 0; j < N; j++) {
                    int distance = graph[i][j];
                    if (distance > 0) {//代表i节点与j节点存在边
                        /*
                        如果start -> i -> j的距离     <     start -> j的距离
                        则更新result[j]
                         */
                        if (result[j] > result[i] + distance) {
                            update = true;//这次循环中存在更新操作
                            result[j] = result[i] + distance;
                        }
                    }
                }
            }
            if (!update) {//判断这次循环中有没有更新操作
                break;
            }
        }
        return result;
    }
}
